//
// Created by durandal on 2024/1/18.
//

#ifndef ALGORITHM_TREE_H
#define ALGORITHM_TREE_H

#include <iostream>
#include <functional>

template<typename T>
struct node_ {
    T element_;

    // for binary tree
    node_* lchild_;
    node_* rchild_;

    // 用于线索二叉树
    node_* l_clue_child_ = NULL;
    node_* r_clue_child_ = NULL;

    // 判断这个node是否添加了线索
    bool clue_flag_;

    node_(T && element, node_* lchild = NULL, node_* rchild = NULL, node_* l_clue_child = NULL, node_* r_clue_child = NULL, bool clue_flag = false)
        : element_(element), lchild_(lchild), rchild_(rchild), l_clue_child_(l_clue_child), r_clue_child_(r_clue_child), clue_flag_(clue_flag) {}
    node_(const T & element, node_* lchild = NULL, node_* rchild = NULL, node_* l_clue_child = NULL, node_* r_clue_child = NULL, bool clue_flag = false)
        : element_(element), lchild_(lchild), rchild_(rchild), l_clue_child_(l_clue_child), r_clue_child_(r_clue_child), clue_flag_(clue_flag) {}
};

template<typename T>
class BinaryTree {
public:
    const static int PRE = 0;
    const static int IN = 1;
    const static int POST = 2;

    BinaryTree(): root_(NULL), thread_(false) { }

    virtual ~BinaryTree() {
        std::function<void(node_<T>*)> releaseNodeFunc = [](node_<T>* node) { delete node; };
        postorderTraversal(this->root_, releaseNodeFunc);
    }

    BinaryTree(BinaryTree<T>&& other)  noexcept {
        this->thread_ = other.thread_;
        this->root_ = other.root_;
        other.thread_ = false;
        other.root_ = NULL;
    }

    BinaryTree(const BinaryTree<T>& other)
      : thread_(other.thread_)
    {
        std::function<node_<T>*(const node_<T>*)> func = [&func](node_<T>* node) -> node_<T>* {
            if (node == NULL)
                return NULL;

            node_<T>* newNode = new node_(node->element_, NULL, NULL);
            newNode->lchild_ = func(node->lchild_);
            newNode->rchild_ = func(node->rchild_);

            return newNode;
        };
    }

    void buildFromValueList(T* list, T invalidValue, std::function<void(T** list)> buildFunc) {
        buildFunc(list);
    }

    void printInOrder(int flag) const {
        std::function<void(node_<T>*)> printFunc = [](node_<T>* node) { std::cout << node->element_; };
        this->traversalByFlag(flag, printFunc);
        std::cout<<std::endl;
    }

    void thread(int flag) {
        node_<T>* pre_node = NULL;
        std::function<void(node_<T>*)> threadFunc = [&pre_node](node_<T>* node) {
            if (node->lchild_ == NULL) {
                node->l_clue_child_ = pre_node;
                node->clue_flag_ = true;
            }

            if (pre_node != NULL && pre_node->rchild_ == NULL) {
                pre_node->r_clue_child_ = node;
                pre_node->clue_flag_ = true;
            }

            pre_node = node;
        };

        std::function<void(node_<T>*)> clearFunc = [](node_<T>* node) {
            node->r_clue_child_ = node->l_clue_child_ = NULL;
            node->clue_flag_ = false;
        };

        preorderTraversal(this->root_, clearFunc);

        this->thread_ = true;
        traversalByFlag(flag, threadFunc);

    }

    BinaryTree<T> asthread(int flag) {
        BinaryTree<T> new_tree = *this;
        new_tree.thread(flag);
        return std::move(new_tree);
    }

    // expose root to public, just 4 test
    node_<T>* get_root_FOR_TEST() { return this->root_; }
    void set_root_FOR_TEST(node_<T>* p) { this->root_ = p; }

protected:
    void traversalByFlag(int flag, std::function<void(node_<T>*)> traversalFunc) {
        if (flag == BinaryTree::IN)
            inorderTraversal(this->root_, traversalFunc);
        else if (flag == BinaryTree::PRE)
            preorderTraversal(this->root_, traversalFunc);
        else if (flag == BinaryTree::POST)
            postorderTraversal(this->root_, traversalFunc);
        else {
            // log fatal
        }
    }

    void traversalByFlag(int flag, std::function<void(node_<T>*)> traversalFunc) const {
        if (flag == BinaryTree::IN)
            inorderTraversal(this->root_, traversalFunc);
        else if (flag == BinaryTree::PRE)
            preorderTraversal(this->root_, traversalFunc);
        else if (flag == BinaryTree::POST)
            postorderTraversal(this->root_, traversalFunc);
        else {
            // log fatal
        }
    }

    static void preorderTraversal(node_<T>* root, std::function<void(node_<T>*)> traversalFunc) {
        if (root) {
            traversalFunc(root);
            preorderTraversal(root->lchild_, traversalFunc);
            preorderTraversal(root->rchild_, traversalFunc);
        }
    }

    static void postorderTraversal(node_<T>* root, std::function<void(node_<T>*)> traversalFunc) {
        if (root) {
            postorderTraversal(root->lchild_, traversalFunc);
            postorderTraversal(root->rchild_, traversalFunc);
            traversalFunc(root);
        }
    }

    static void inorderTraversal(node_<T>* root, std::function<void(node_<T>*)> traversalFunc) {
        if (root) {
            inorderTraversal(root->lchild_, traversalFunc);
            traversalFunc(root);
            inorderTraversal(root->rchild_, traversalFunc);
        }
    }

    node_<T>* root_;

    bool thread_;

};


#endif //ALGORITHM_TREE_H
